package linked_list

import "fmt"

const MAXSIZE = 20

type ElemType int64

//有序列表---列表的顺序表示
type SqList struct {
	length int64             //长度
	data   [MAXSIZE]ElemType //具体内容
}

//获取长度
func (s *SqList) Length() int64 {
	return s.length
}

//获取指定index处元素
func (s *SqList) GetElemByIndex(index int64) (ElemType, error) {
	if index < 0 || index > s.length-1 {
		return 0, fmt.Errorf("invalid index")
	}

	return s.data[index], nil
}

//获取指定元素
func (s *SqList) GetElem(val ElemType) (int64, error) {
	var i int64
	//遍历查找
	for i = 0; i < s.length-1; i++ {
		if s.data[i] == val {
			return i, nil
		}
	}
	return 0, fmt.Errorf("Val not found")
}

//在index处后面插入元素
//
//插入算法的思路：
//如果插入位置不合理，抛出异常；
//如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
//从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
//将要插入元素填入位置i处； ?表长加1。”
//
//摘录来自: 程杰. “大话数据结构。” Apple Books.
func (s *SqList) InsertElem(index int64, val ElemType) error {
	//检查位置是否合法
	if index < 0 || index > s.length {
		return fmt.Errorf("invalid index")
	}

	//检查列表是否已满
	if s.length == MAXSIZE {
		return fmt.Errorf("list is full")
	}

	//如果index不是位于末尾，需要处理元素后移
	if index <= s.length-1 {
		//从index处(含index)，所有的元素后移
		var k int64
		for k = s.length - 1; k >= index; k-- {
			s.data[index+1] = s.data[index]
		}
	}

	s.data[index] = val
	s.length++

	return nil
}

//新增元素
func (s *SqList) Append(val ElemType) error {
	if s.length == MAXSIZE {
		return fmt.Errorf("list is full")
	}
	s.length++
	s.data[s.length-1] = val
	return nil
}

//删除元素
func (s *SqList) DeleteElem(index int64) error {
	if index < 0 || index > s.length-1 {
		return fmt.Errorf("invalid index")
	}

	if s.length == 0 {
		return fmt.Errorf("empty list")
	}

	//如果不是删除最后一个, 删除元素需要将元素前移
	if index < s.length-1 {
		var k int64
		for k = index; k < s.length-1; k++ {
			s.data[index] = s.data[index+1]
		}
	}

	s.length--

	return nil
}

//打印列表
func (s *SqList) PrintList() error {
	var i int64
	for i = 0; i <= s.length-1; i++ {
		fmt.Printf("%d ", s.data[i])
	}
	fmt.Println("")
	return nil
}
